package algorithms.leaning.class21;

import common.util.MyUtil;

import java.util.HashMap;
import java.util.Map;

/**
 * arr是货币数组，其中的值都是正数。再给定一个正数aim。
 * 每个值都认为是一张货币，
 * 认为值相同的货币没有任何不同，
 * 返回组成aim的方法数
 * 例如：arr = {1,2,1,1,2,1,2}，aim = 4
 * 方法：1+1+1+1、1+1+2、2+2
 * 一共就3种方法，所以返回3
 *
 * @author guichang
 * @date 2021/6/22
 */

@SuppressWarnings("all")
public class Code4_动态规划_货币组成_限制张数 {

    public static void main(String[] args) {
        int[] arr = {1, 2, 1, 1, 2, 1, 2};
        int aim = 4;

        MyUtil.print(ways(arr, aim));
        MyUtil.print(waysDp(arr, aim));
        MyUtil.print(waysDp2(arr, aim));
    }

    public static int ways(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        // key=面值 value=张数
        Map<Integer, Integer> map = new HashMap<>();
        for (int key : arr) {
            map.put(key, map.get(key) == null ? 1 : map.get(key) + 1);
        }
        int index = 0;
        int size = map.size();
        int[] face = new int[size];
        int[] paper = new int[size];
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            face[index] = entry.getKey();
            paper[index++] = entry.getValue();
        }

        return process(face, paper, 0, aim);
    }

    private static int process(int[] face, int[] paper, int index, int rest) {
        if (index == face.length) {
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        for (int i = 0; i <= paper[index] && rest >= i * face[index]; i++) {
            ways += process(face, paper, index + 1, rest - i * face[index]);
        }
        return ways;
    }

    public static int waysDp(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        // key=面值 value=张数
        Map<Integer, Integer> map = new HashMap<>();
        for (int key : arr) {
            map.put(key, map.get(key) == null ? 1 : map.get(key) + 1);
        }
        int in = 0;
        int size = map.size();
        int[] face = new int[size];
        int[] paper = new int[size];
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            face[in] = entry.getKey();
            paper[in++] = entry.getValue();
        }

        int[][] dp = new int[size + 1][aim + 1];
        dp[size][0] = 1;
        for (int index = size - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for (int i = 0; i <= paper[index] && rest >= i * face[index]; i++) {
                    ways += dp[index + 1][rest - i * face[index]];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }

    public static int waysDp2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        // key=面值 value=张数
        Map<Integer, Integer> map = new HashMap<>();
        for (int key : arr) {
            map.put(key, map.get(key) == null ? 1 : map.get(key) + 1);
        }
        int in = 0;
        int size = map.size();
        int[] face = new int[size];
        int[] paper = new int[size];
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            face[in] = entry.getKey();
            paper[in++] = entry.getValue();
        }

        int[][] dp = new int[size + 1][aim + 1];
        dp[size][0] = 1;
        for (int index = size - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest - face[index] >= 0) {
                    dp[index][rest] += dp[index][rest - face[index]];
                }
                // 减去张数+1的位置
                if(rest - face[index] * (paper[index] + 1) >= 0) {
                    dp[index][rest] -= dp[index][rest - face[index] * (paper[index] + 1)];
                }
            }
        }
        return dp[0][aim];
    }


}